/**
 * @a https://leetcode.cn/problems/permutations/
 */

#include "../common.h"

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
private:
    vector<vector<int>> res;
    void dfs(vector<int> nums, int x) {
        if (x == nums.size() - 1) {
            res.push_back(nums);      // 添加排列方案
            return;
        }
        for (int i = x; i < nums.size(); i++) {
            swap(nums[i], nums[x]);   // 交换，将 nums[i] 固定在第 x 位
            dfs(nums, x + 1);         // 开启固定第 x + 1 位元素
            swap(nums[i], nums[x]);   // 恢复交换
        }
    }
};

class Solution {
private:
    vector<vector<int>> ret;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> tmp = nums;
        dfs(tmp,0);
        return ret;
    }
private:
    void dfs(vector<int>& nums, int index){
        if(index == nums.size() - 1){
            ret.push_back(nums);
            return;
        }
        for(int i = index; i < nums.size(); i++){
            swap(nums[i], nums[index]);
            dfs(nums, index + 1);
            swap(nums[i], nums[index]);
        }
    }
};
// class Solution {
// public:
//     vector<vector<int>> permute(vector<int>& nums) {
//         if(nums.size()) return {};
//         // 感觉可以递归
//         int n = nums.size();
//         int nr = 1;
//         while(n--) nr *= n;
//         n = nums.size();
//         vector<vector<int>> ans(nr,vector<int>(n,0));
        

//     }
// };